The present invention relates to a method and apparatus for determining waveform factors for forming transmitting and receiving beams for an array of transmitting or receiving elements in an acoustic system for imaging in non-homogenous or non-uniform mediums and, in particular, wherein the number of waveform delays required to form the optimal transmitting or receiving beams is greater than the number of signal channels for providing the waveforms to the transmitting elements or collecting from the receiving elements.
There are many acoustic imaging systems that require the controlled, directional transmission or reception of sound energy in non-homogenous or non-uniform mediums and in frequency ranges extending from the ultrasonic frequencies and through the audible frequencies to the sub-audible frequencies. Examples of such could range from ultrasonic medical imaging systems to geological imaging or profiling systems and are characterized in that the medium or environment in which the imaging or profiling is to be performed is non-homogenous or non-uniform. That is, the mediums through which such systems form transmitting and receiving beams are non-homogenous, being comprised of layers or bodies or masses of differing materials, and as a consequence have transmission characteristics that vary significantly and non-uniformly from point to point through the medium. For example, ultrasonic medical imaging systems are required to form imaging transmission or receiving beams in the human body, which is a complex structure formed of bone, muscle, fluids and other tissues. Geological imaging and profiling systems are likewise required to form imaging receiving beams in a medium formed of layers and masses of different rocks, soils and liquids typically having widely varying transmission characteristics. In contrast, air acoustic systems, sonar systems and radar systems operate in mediums that are relatively homogenous and uniform. That is, the mediums in which they operate, such as air or water, are comprised of the same substance throughout and, as a consequence and although the transmission characteristics of the air or water may vary noticeably from point to point, have relatively uniform transmission characteristics compared to the human body or geological structures. It will therefore be apparent that the beamforming requirements imposed on acoustic systems for operating in non-homogenous and non-uniform mediums, hereafter referred to as non-homogenous/non-uniform acoustic systems, are often more stringent than those imposed on systems operating in homogenous or uniform mediums. For example, non-homogenous/non-uniform acoustic imaging systems are frequently required to form transmitting or receiving beams that xe2x80x9clook around, through or betweenxe2x80x9d the components of complex structures made of substances having widely varying characteristics.
One common technique for the controlled, directional transmission or reception of acoustic energy in non-homogenous/non-uniform acoustic imaging systems is the use of arrays of acoustic transmitting and receiving elements, which are often referred to as xe2x80x9cphased arraysxe2x80x9d. In this method, the elements of an array, which are generally but not necessarily identical units, are arranged in a predetermined two or three dimensional geometric relationship and the directional pattern or patterns of transmission or reception of the array, often referred to as xe2x80x9cbeamsxe2x80x9d, are determined by the combination of the patterns of transmission or reception of the individual elements of the array. In particular, the directions and shapes of the beams are determined by the transmission and reception patterns of the individual elements, the geometric relationship between the elements and the phase relationships among the signals used to drive the elements or received from the elements. Of these, the geometric arrangement of the elements and the characteristics of the elements are generally fixed and the phase relationships among the signals driving or received from the elements are typically controlled to form and direct the xe2x80x9cbeamsxe2x80x9d of the array.
It is well understood that a phased array in a non-homogenous/non-uniform acoustic imaging system can form a transmitting or receiving beam of a desired pattern or shape and can direct the beam in an arbitrary direction by appropriate selection and control of the phase relationships among the transmitted or received signals. In a typical phased array non-homogenous/non-uniform acoustic imaging system, the selection and control of the phase relationships among the signals is accomplished by selection and control of time delays through the signal channels through which driving signals are provided to the array elements or the received signals are received from the array elements. It is commonly understood that if each element is provided with its own independent signal channel these delays can be chosen optimally to provide the best possible beam, subject to the physical constraints of the geometry of the array, the number and characteristic of the array elements and the signal waveforms. This result can also be achieved where the number of available signal channels is greater than the number of array elements, or when the geometry of the array is symmetric with respect to the desired beam or beams so that the number of required unique delays is reduced to less than the number of signal channels and so that, for example, one channel can be used for more than one array element.
It is a commonly occurring problem, however, that the number of required delays is greater than the number of available signal channels and it is then necessary for at least some of the array elements to share one or more of the channels, that is, to be grouped or wired together and connected to a channel. In such instances, each such group of array elements connected from a single signal channel operates as a single array element and it is often difficult to obtain the optimum beam or beams from the array, or even a close approximation of the optimum beams. It is possible in theory, however, to obtain a beam or beams that are close to the optimum beam or beams if the Nyquist criterion for spatial sampling can be satisfied by the array and if appropriate groupings of the array elements and corresponding signal channel delay times can be determined and implemented in a realizable system.
In general, the methods of the prior art for determining groupings of acoustic array elements and sets of signal channel delay times have attempted to find the array element groupings and channel delay times that provide beams that match, as closely as possible, the beams formed in the optimum situation wherein the number of available signal channels is equal to the number of array elements. In those instances wherein the optimum required delays fall into localized clusters of values such that the number of such clusters of values is equal to or less than the number of available signal channels, a reasonable solution is to choose a delay time for each channel that is equal to the center, or average, of a corresponding cluster of delay time values and, thereby, the corresponding group of array elements. In general, however, the set of optimum delay time values will be irregularly scattered between some minimum value and some maximum value and the selection of a set of delay times that optimally approximates the optimum delay time values is unobvious and difficult, at best.
One method that has been used to find a set of delay times that acceptably approximate the optimum delay time values has been to find a set of delay times that minimizes the sum of the squares of the differences between each optimum delay time value and the closest delay of the set of approximate delay times. Determining such a set is a non-linear problem, however, since small changes in the delay times selected to represent the optimum delay time values may cause a change in the correspondence between any given optimum delay time value and the delay time that represents that optimum delay time value, in effect causing an array element to move from one group of array elements to another group of array elements. This non-linearity renders the usual approaches to such problems, such as least squares approximation, ineffective.
The present invention provides a solution to these and other problems of the prior art by providing a method for determining the groupings of acoustic array elements and the corresponding signal channel delay times to allow the selectable and arbitrary formation and steering of beams by a non-homogenous/non-uniform acoustic imaging system, and a mechanism for controlling the distribution of appropriately delayed waveforms to the groups of array elements, assuming that there are no arbitrary array element grouping constraints, that is, that any element may be grouped with any other element or group of elements.
The present invention is directed to a method for use in a non-homogenous/non-uniform acoustic imaging system for determining beamform factors for forming acoustic beams approximating an optimum acoustic beam for the directional transmission or reception of acoustic energy by a non-homogenous/non-uniform acoustic imaging system wherein the non-homogenous/non-uniform acoustic imaging system includes a first plurality of acoustic elements connectable to a second plurality of signal channels wherein the first plurality is greater than the second plurality, and an apparatus for use in a non-homogenous/non-uniform acoustic imaging system for performing the method of the present invention.
The method of the present invention includes the steps of determining, from a set of initial beamform factors, at least one dependent beamform factor of at least one optimum beam to be formed by the non-homogenous/non-uniform acoustic imaging system, and determining the maximum and minimum values of the dependent beamform factors. The method then generates a parent population of chromosomes wherein each chromosome includes a gene for and corresponding to each dependent beamform factor and represents a candidate beamformed by the phased array non-homogenous/non-uniform acoustic imaging system for the initial beamform factors and the dependent beamform factors represented by the genes of the chromosome. According to the present invention, the generation of a parent population is accomplished by generating a first parent population wherein the value of each gene corresponding to a dependent beamform factor has a value between the maximum and minimum values of the corresponding dependent beamform factor and by generating a subsequent parent population by cloning of the chromosomes of a surviving population.
The method of the present invention then generates a child population from the parent population by exchanging statistically selected pairs of genes of the chromosomes of the parent population and generating a mutated population from the child population by mutating statistically selected genes of the child population. A surviving population is then selected from the mutated population by comparing the chromosomes of the mutated population with a fitness criteria based upon at least one optimum beamform factor and selecting for the surviving population the chromosomes of the mutated population meeting the fitness criteria.
Finally, the method of the present invention compares the chromosomes of the surviving population with a solution criteria and, when at least one chromosome of the surviving population meets the solution criteria, provides the genes of the chromosome of the surviving population having the best match to the fitness criteria as the dependent beamform factors for forming a beam approximating the optimum beam.
According to the present invention, the solution criteria may be a predetermined number of iterations of the generation of a surviving population. Alternatively, the solution criteria may be a predetermined tolerance of difference between a chromosome of a current surviving population having the best match to the fitness criteria and a chromosome of a preceding surviving population having the best match to the fitness criteria wherein the solution criteria is met when the difference between the chromosome having the best match to the fitness criteria of the current surviving population is within the predetermined tolerance of difference from the chromosome of the preceding surviving population. In yet another implementation, the fitness criteria may be a predetermined tolerance of difference between a beamform factor determined by the genes of a chromosome of a current surviving population and the optimum beamform factors.
In further implementations of the present invention, each parent generation may be generated to have a constant number of chromosomes and the chromosomes of each surviving population may be cloned to generate a new parent population so that the proportionate representation of each chromosome of a surviving population in a new parent population is proportionate to a measure of fitness of the chromosome of the surviving population with respect to the fitness criteria.
In yet further implementations of the present invention, a chromosome of a surviving population may be selected to that the chromosome of a surviving population having a best measurement of fitness with respect to the fitness criteria will be represented in the parent population cloned from the surviving population.
In yet further implementations of the invention, each chromosome of a child population may be generated by statistical selection and exchange of genes of chromosomes of the parent population and each mutated generation may be generated by statistical selection and variation of the values of the genes of corresponding chromosomes of the child generation within predetermined limits.
The present invention further includes a non-homogenous/non-uniform acoustic imaging system implementing the present invention wherein the non-homogenous/non-uniform acoustic imaging system includes a beamform processor including a memory and a processor for executing the beamform process and generating from initial beamform factors first and second dependent beamform factors. The non-homogenous/non-uniform acoustic imaging system further includes a waveform processor connected to the signal channels and responsive to the first dependent beamform factors for applying the first dependent beamform factors to a corresponding second plurality of element group signals, an array switch connected between the signal channels and the array elements and responsive to the second dependent beamform factors for selectively connecting the signal channels to the array elements of the element groups, and a switch configuration table connected from the beamform generator and to the array switch for storing and providing to the array switch the second dependent beamform factors.
The beamform process executed by the beamform generator includes determining from a set of initial beamform factors at least one dependent beamform factor of at least one optimum beam to be formed by the non-homogenous/non-uniform acoustic imaging system, determining the maximum and minimum values of the dependent beamform factors, and generating a parent population of chromosomes wherein each chromosome includes a gene for and corresponding to each dependent beamform factor and represents a candidate beamformed by the phased array non-homogenous/non-uniform acoustic imaging system for the initial beamform factors and the dependent beamform factors represented by the genes of the chromosome. The process of generating a parent population includes generating a first parent population wherein the value of each gene corresponding to a dependent beamform factor has a value between the maximum and minimum values of the corresponding dependent beamform factor and generating a subsequent parent population by cloning of the chromosomes of a surviving population.
The process includes generating a child population from the parent population by exchanging statistically selected pairs of genes of the chromosomes of the parent population, and generating a mutated population from the child population by mutating statistically selected genes of the child population. The process further includes selecting the surviving population from the mutated population by comparing the chromosomes of the mutated population with a fitness criteria based upon an optimum beamform factor and selecting for the surviving population the chromosomes of the mutated population meeting the fitness criteria. The process then includes comparing the chromosomes of the surviving population with a solution criteria and, when at least one chromosome of the surviving population meets the solution criteria, providing the genes of the chromosome of the surviving population having the best match to the fitness criteria as the first and second dependent beamform factors for forming a beam approximating the optimum beam.
In many non-homogenous/non-uniform acoustic imaging systems, the waveform processor is a signal generator and a signal processor and the corresponding second plurality of element group signals are signals to be emitted by the array elements of the corresponding element groups and signals received by the array elements of the corresponding element groups.
Other features, objects and advantages of the present invention will be understood by those of ordinary skill in the relevant arts after reading the following descriptions of a presently preferred embodiment of the present invention, and after examination of the drawings, wherein: